The present invention relates to methods and systems for providing three-dimensional representations and will be described below with reference to this application. However, it will be appreciated that the invention is not limited to this particular field of use.
Several methods for providing volumetric representations of three-dimensional objects are known in the art. An example of a method for providing volumetric representations of three-dimensional objects includes providing a three-dimensional (3D) shape reconstruction of objects from multiple views. The computation of the visual hull from object silhouettes is a popular technique.
The method, also called shape-from-silhouette, delivers a 3D description of the object. The approach requires a set of silhouette images from calibrated cameras. A silhouette image is a binary (or in some cases, grey scale) image where each pixel indicates whether this pixel belongs to the object or not. The silhouette information can be determined by any suitable segmentation process. This is advantageously done using chroma-keying or difference-keying as described in our GB-0220972.4 and our earlier applications referred therein.
The 3D shape reconstruction can be formulated as the intersection of generalised cones of the silhouette images. A generalised cone is the union of visual rays from all silhouette points of a particular image. This intersection gives only an approximation of the real object shape and is called the visual hull. In particular concavities cannot be modeled with this method.
Several algorithms have been published for the computation of the visual hull, for example: W. Martin and J. K. Aggarwal, “Volumetric descriptions of objects from multiple views,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 5, no. 2, pp. 150–158, March 1983; M. Potmesil, “Generating octree models of 3D objects from their silhouettes in a sequence of images,” Computer Vision, Graphics and Image Processing, vol. 40, pp. 1–29, 1987; Richard Szeliski, “Rapid octree construction from image sequences,” CVGIP: Image Understanding, vol. 58, no. 1, pp. 23–32, July 1993; and Wolfgang Niem, “Robust and fast modeling of 3d natural objects from multiple views,” in SPIE Proceedings, Image and Video Processing II, San Jose, February 1994, vol. 2182, pp. 388–397. These approaches attempt to solve the problem in a volumetric space representation. The most common of these representations is to subdivide a 3D box in euclidian 3-space into a set of voxels of discrete size. The size of the box is predetermined such that the object can fit inside. In order to save memory these may be represented as “octrees” or are run-length encoded.
For the use of the 3D reconstruction, e.g. in a computer graphic application, a surface description, usually a polygonal mesh has to be generated. An often used algorithm is the marching cubes algorithm, described in U.S. Pat. Nos. 4,710,876 and 4,885,688, which creates an iso-surface of a volumetric data set. Since the mentioned shape-from-silhouette methods compute binary voxels the 3D surfaces generated from those using the marching cube algorithm are very noisy. This noise is introduced due to spatial discretisation of the volumetric representations. That is to say, real data as the actual shape of the object is lost during the processing of the algorithm.